package xin.luna.structs;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class StackResizeArrayList<Item> implements Iterable<Item> {
  private Item[] list;

  private int length;

  @SuppressWarnings("unchecked")
  public StackResizeArrayList(int cap) {
    list = (Item[]) new Object[cap];
  }

  public static void main(String[] args) {
    StackResizeArrayList<String> s = new StackResizeArrayList<>(1);
    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) {
        s.push(item);
      } else if (!s.isEmpty()) {
        StdOut.print(s.pop() + "  ");
      }
    }

    StdOut.println("(" + s.size() + " left on stack)");
  }

  public boolean isEmpty() {
    return 0 == length;
  }

  public int size() {
    return length;
  }

  public boolean isFull() {
    return length == list.length;
  }

  public void push(Item item) {
    if (isFull()) resize(list.length + Math.max(list.length / 2, 1));

    list[length++] = item;
  }

  public Item pop() {
    Item item = list[--length];
    list[length] = null;

    if (length > 0 && length == list.length / 4) resize(list.length / 2);

    return item;
  }

  @Override
  public Iterator<Item> iterator() {
    return new StackIterator();
  }

  @SuppressWarnings("unchecked")
  private void resize(int max) {
    Item[] newArray = (Item[]) new Object[max];

    System.arraycopy(list, 0, newArray, 0, length);

    list = newArray;
  }

  private class StackIterator implements Iterator<Item> {
    int iLength = length;

    @Override
    public boolean hasNext() {
      return 0 == iLength;
    }

    @Override
    public Item next() {
      if (0 == iLength) throw new NoSuchElementException();

      return list[--iLength];
    }

    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }
}
